#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/8 15:50
# @USER    : Shengji He
# @File    : WorldLadder.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from collections import defaultdict
from typing import List


class Solution:
    def __init__(self):
        self.length = 0
        # Dictionary to hold combination of words that can be formed,
        # from any given word. By changing one letter at a time.
        self.all_combo_dict = defaultdict(list)

    def visitWordNode(self, queue, visited, others_visited):
        current_word, level = queue.pop(0)
        for i in range(self.length):
            # Intermediate words for current word
            intermediate_word = current_word[:i] + "*" + current_word[i + 1:]
            # Next states are all the words which share the same intermediate state.
            for word in self.all_combo_dict[intermediate_word]:
                # If the intermediate state/word has already been visited from the
                # other parallel traversal this means we have found the answer.
                if word in others_visited:
                    return level + others_visited[word]
                if word not in visited:
                    # Save the level as the value of the dictionary, to save number of hops.
                    visited[word] = level + 1
                    queue.append((word, level + 1))
        return None

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        """
        Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest
        transformation sequence from beginWord to endWord, such that:
            - Only one letter can be changed at a time.
            - Each transformed word must exist in the word list.
        Note:
            - Return 0 if there is no such transformation sequence.
            - All words have the same length.
            - All words contain only lowercase alphabetic characters.
            - You may assume no duplicates in the word list.
            - You may assume beginWord and endWord are non-empty and are not the same.
        Example 1:
        Input:
            beginWord = "hit",

            endWord = "cog",

            wordList = ["hot","dot","dog","lot","log","cog"]

        Output: 5

        Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",

        return its length 5.

        Example 2:

        Input:
            beginWord = "hit"

            endWord = "cog"

            wordList = ["hot","dot","dog","lot","log"]

        Output: 0

        Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.


        :param beginWord: str
        :param endWord: str
        :param wordList: List[str]
        :return: int
        """
        # if endWord not in wordList:
        #     return 0
        # wordList.append(beginWord)
        # wordList = list(set(wordList))
        # if len(beginWord) == 1 or (len(beginWord) - sum([i == j for i, j in zip(list(beginWord), list(endWord))]) == 1):
        #     return 2
        # buckets = defaultdict(list)
        # for word in wordList:
        #     for i in range(len(beginWord)):
        #         match = word[:i] + '_' + word[i + 1:]
        #         buckets[match].append(word)
        # # BFS
        # toSeen = deque([(beginWord, 1)])
        # beFound = {beginWord: 1}
        # while toSeen:
        #     curWorld, level = toSeen.popleft()
        #     for i in range(len(beginWord)):
        #         match = curWorld[:i] + '_' + curWorld[i + 1:]
        #         for word in buckets[match]:
        #             if word == endWord:
        #                 return level + 1
        #             if word not in beFound:
        #                 beFound[word] = level + 1
        #                 toSeen.append((word, level + 1))
        #         buckets[match] = []
        # return 0
        if endWord not in wordList or not endWord or not beginWord or not wordList:
            return 0
        # Since all words are of same length.
        self.length = len(beginWord)
        for word in wordList:
            for i in range(self.length):
                # Key is the generic word
                # Value is a list of words which have the same intermediate generic word.
                self.all_combo_dict[word[:i] + "*" + word[i + 1:]].append(word)

        # Queues for birdirectional BFS
        queue_begin = [(beginWord, 1)]  # BFS starting from beginWord
        queue_end = [(endWord, 1)]  # BFS starting from endWord

        # Visited to make sure we don't repeat processing same word
        visited_begin = {beginWord: 1}
        visited_end = {endWord: 1}
        ans = None

        # We do a birdirectional search starting one pointer from begin
        # word and one pointer from end word. Hopping one by one.
        while queue_begin and queue_end:
            # One hop from begin word
            ans = self.visitWordNode(queue_begin, visited_begin, visited_end)
            if ans:
                return ans
            # One hop from end word
            ans = self.visitWordNode(queue_end, visited_end, visited_begin)
            if ans:
                return ans
        return 0


if __name__ == '__main__':
    # beginWord = "hit"
    # endWord = "cog"
    # wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
    # beginWord = "hot"
    # endWord = "dog"
    # wordList = ["hot", "dog", "dot"]
    beginWord = "qa"
    endWord = "sq"
    wordList = ["si", "go", "se", "cm", "so", "ph", "mt", "db", "mb", "sb", "kr", "ln", "tm", "le", "av", "sm", "ar",
                "ci", "ca", "br", "ti", "ba", "to", "ra", "fa", "yo", "ow", "sn", "ya", "cr", "po", "fe", "ho", "ma",
                "re", "or", "rn", "au", "ur", "rh", "sr", "tc", "lt", "lo", "as", "fr", "nb", "yb", "if", "pb", "ge",
                "th", "pm", "rb", "sh", "co", "ga", "li", "ha", "hz", "no", "bi", "di", "hi", "qa", "pi", "os", "uh",
                "wm", "an", "me", "mo", "na", "la", "st", "er", "sc", "ne", "mn", "mi", "am", "ex", "pt", "io", "be",
                "fm", "ta", "tb", "ni", "mr", "pa", "he", "lr", "sq", "ye"]
    # beginWord = "hit"
    # endWord = "cog"
    # wordList = ["hot","dot","dog","lot","log"]
    S = Solution()
    print(S.ladderLength(beginWord, endWord, wordList))
    print('done')
